package com.husd.leetcode.sort;

import java.util.Arrays;

/**
 *
 * 快速排序的基本思想：挖坑填数+分治法
 * 1. 从序列当中选择一个基准数(pivot) 在这里我们选择序列当中第一个数最为基准数
 * 2. 将序列当中的所有数依次遍历，比基准数大的位于其右侧，比基准数小的位于其左侧
 * 3. 重复步骤1.2，直到所有子集当中只有一个元素为止。 用伪代码描述如下：
 * 1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
 * 2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
 * 3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
 * 4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中
 */
public class QuickSort {

    //快速排序 分治办法
    private static void sort(int[] a, int head, int tail) {

        int low = head;
        int high = tail;
        //pivot 就是基准值，比它小的放左边，比它大的放右边
        int pivot = a[low];
        if (low < high) {

            while (low < high) {
                while (low < high && pivot <= a[high]) {
                    high--;
                }
                a[low] = a[high];
                while (low < high && pivot >= a[low]) {
                    low++;
                }
                a[high] = a[low];
            }
            a[low] = pivot;

            if (low > head + 1) sort(a, head, low - 1);
            if (high < tail - 1) sort(a, high + 1, tail);
        }
    }

    //快速排序 分治办法
    private static void sort2(int[] a, int head, int tail) {

        int low = head;
        int high = tail;

        int pivot = a[low];

        if (low < high) {

            while(low < high) {
                while(low <high && pivot <= a[high]) {
                    high--;
                }
                a[low] = a[high];
                while(low < high && pivot >= a[low]) {
                    low--;
                }
                a[high] = a[low];
            }

            a[low] = pivot;
            if (low > head + 1) {
                sort2(a, head, low - 1);
            }
            if (high < tail - 1) {
                sort2(a, high + 1, tail);
            }
        }

    }

    public static void main(String[] args) {

        int[] a = {5, 4, 3, 2, 10, 6, 7, 1, 8, 9};
        int n = a.length;
        QuickSort.sort(a, 0, n - 1);
        System.out.println(Arrays.toString(a));
    }
}
